L2-004 这是二叉搜索树吗？

题目 L2-004 这是二叉搜索树吗？

思路分析

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

const int N=1010;

int pre[N];

vector<int> ans;

bool is_mirror=false;

void dfs(int l,int r){

	if(l>r)	return;

	int i = l+1,j=r;

	if(!is_mirror){

		while(i<=r && pre[i]<pre[l])	i++;

		while(j>=l+1 && pre[j]>=pre[l])	j--;

	}else{

		while(i<=r && pre[i]>=pre[l])	i++;

		while(j>=l+1 && pre[j]<pre[l])	j--;

	}

	if(abs(i-j)!=1)	return;

	dfs(l+1,j);

	dfs(i,r);

	ans.push_back(pre[l]);

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n;cin>>n;

	for(int i=0;i<n;i++)	cin>>pre[i];

	dfs(0,n-1);

	if(ans.size() != n){

		is_mirror = true;

		ans.clear();

		dfs(0,n-1);

	}

	if(ans.size() != n){

		cout<<"NO"<<endl;

	}else{

		cout<<"YES"<<endl;

		for(int i=0;i<n;i++){

			if(i)	cout<<" ";

			cout<<ans[i];

		}

	}

	return 0;

}

同类题型

视频讲解

⬅️ L2-003 月饼 🏠 00-天梯赛 ➡️ L2-005 集合相似度